package com.yun.algorithmproblem.huaweiod;

import java.util.*;

public class HJ16 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N;
        int m;
        ArrayList<int[]> commodity = new ArrayList<>();
        N = in.nextInt();
        m = in.nextInt();
        for (int i = 0; i < m; i++) {
            int[] vpq = new int[3];
            vpq[0] = in.nextInt() / 10;
            vpq[1] = in.nextInt();
            vpq[2] = in.nextInt();
            commodity.add(vpq);
        }
        for (int[] ints : commodity) {
            System.out.println(Arrays.toString(ints));
        }
        System.out.println(maxSatisfied(N / 10, m, commodity));
    }

    static int maxSatisfied(int N, int m, ArrayList<int[]> commodity) {
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        for (int i = 1; i < commodity.size() + 1; i++) {
            //i为当前物品的编号,从0开始
            int[] vpq = commodity.get(i - 1);
            //vpq[2]表示当前物品是否为主件
            if (vpq[2] == 0) {//主件
                map.computeIfAbsent(i, key -> new ArrayList<Integer>());
            } else {//附件 vpq[2]为该附件的主件编号
                int mainItemIndex = vpq[2];
                ArrayList<Integer> arrayList = map.computeIfAbsent(mainItemIndex, key -> new ArrayList<>());
                arrayList.add(i);
            }
        }
        for (Integer key : map.keySet()) {
            System.out.print(key+":");
            ArrayList<Integer> arrayList = map.get(key);
            for (Integer i : arrayList) {
                System.out.print(" "+i);
            }
            System.out.println();
        }
        int[] dp = new int[N + 1];
        //此时哈希表中存储的主件的键值都是从编号1开始,注意!
        for (Integer key : map.keySet()) {
            int[] dpTemp=dp;
            int[] vpq = commodity.get(key - 1);
            int satisfaction = vpq[0] * vpq[1];
            dpTemp = dynamic(dp,dpTemp, vpq[0], satisfaction);
            ArrayList<Integer> arrayList = map.get(key);
            if(arrayList.size()==1){
                int[] vpq1=commodity.get(arrayList.get(0)-1);
                int satisfaction1=vpq1[0]*vpq1[1];
                dpTemp=dynamic(dp,dpTemp,vpq[0]+vpq1[0],satisfaction+satisfaction1);
            }else if(arrayList.size()==2){
                int[] vpq1=commodity.get(arrayList.get(0)-1);
                int satisfaction1=vpq1[0]*vpq1[1];
                int[] vpq2=commodity.get(arrayList.get(1)-1);
                int satisfaction2=vpq2[0]*vpq2[1];
                dpTemp=dynamic(dp,dpTemp,vpq[0]+vpq1[0],satisfaction+satisfaction1);
                dpTemp=dynamic(dp,dpTemp,vpq[0]+vpq2[0],satisfaction+satisfaction2);
                dpTemp=dynamic(dp,dpTemp,vpq[0]+vpq1[0]+vpq2[0],satisfaction+satisfaction1+satisfaction2);
            }
            dp=dpTemp;
        }
        return dp[dp.length-1]*10;
    }

    static int[] dynamic(int[] dp,int[] dpTemp, int price, int satisfaction) {
//        System.out.println(price+" "+satisfaction);
//        System.out.println(Arrays.toString(dp));
//        System.out.println(Arrays.toString(dpTemp));
        int[] newDp = new int[dp.length];
        for (int i = 0; i < dp.length; i++) {
            if (i < price) {
                newDp[i] = Math.max(dp[i],dpTemp[i]);
            } else {
                newDp[i] = Math.max(dpTemp[i], dp[i - price] + satisfaction);
            }
        }
        //System.out.println(Arrays.toString(newDp));
        return newDp;
    }
}
